package week1;

public class test5 {
    //斐波那契数列
    //传统方法
    public  static int faibo(int num){
        if(num==1||num==2){
            return 1;
        }
        return faibo(num-1)+faibo(num-2);
    }
    //使用dp优化递归方法
    public static int fibodp(int num){
        int last2=1;
        int last1=1;
        int ret=0;
        for (int i = 3; i <=num; i++) {
            ret=last1+last2;
            last2=last1;
            last1=ret;
        }
        return ret;
    }

    public static void main(String[] args) {
        int num=40;
        System.out.println(faibo(num));
        System.out.println(faibo(num));
    }
}
